package algorithms.leecode;

import java.util.*;

public class Au39 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 关键步骤
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(candidates, len, 0, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param len        冗余变量
     * @param begin      从候选数组的 begin 位置开始搜索
     * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
     * @param path       从根结点到叶子结点的路径
     * @param res
     */
    private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
            if (target - candidates[i] < 0) {
                break;
            }

            // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.addLast(candidates[i]);
            // 调试语句 ①
            // System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));

            // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
            dfs(candidates, len, i + 1, target - candidates[i], path, res);

            path.removeLast();
            // 调试语句 ②
            // System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
        }
    }
    public static int firstMissingPositive(int[] nums) {
        int len  = nums.length;
        int[] res = new int[len+1];

        for(int i = 0;i<len;i++){
            if(nums[i]> 50000){
                continue;
            } else {
                res[nums[i]] = 1;
            }
        }
        for(int i = 1; i < len  ;i++){
            System.err.println(res[i]);
            if(res[i] == 0) {
                return i;
            }
        }

        return -1;

    }


    public static void main(String[] args) {
        System.err.println(Math.pow(10,2));
//        int[] candidates = {0,2,1};
//        firstMissingPositive(candidates);
 //       combinationSum(candidates, 7);
        Map<Character,Integer> map = new HashMap(){{
            put('0',0);
            put('1',1);
            put('2',2);
            put('3',3);
            put('4',4);
            put('5',5);
            put('6',6);
            put('7',7);
            put('8',8);
            put('9',9);
        }};
        char a = '2';
        char b = (char) 9;

        System.err.println(b+'0'=='9');

    }


    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> resultLists = new ArrayList<>();
        for (int i = 0; i < candidates.length; i++) {
            List<Integer> list = new ArrayList<>();

            while (i > 0 && i < candidates.length && candidates[i] == candidates[i - 1]) {
                i++;
            }
            test(candidates, target, i, resultLists, list);
        }
        Set<Integer> set = new HashSet<>(Integer.MAX_VALUE);

        return resultLists;

    }

    public static void test(int[] candidates, int target, int startIndex, List<List<Integer>> resultLists
            , List<Integer> resultList) {

        if (startIndex == candidates.length) {
            return;
        }


        int ans = target - candidates[startIndex];
        List<Integer> copy = new ArrayList<>();
        copy.addAll(resultList);
        copy.add(candidates[startIndex]);

        if (ans == 0) {
            resultLists.add(copy);

        }
        if (ans < 0) {
            return;
        }
        if (ans > 0) {

            for (int k = startIndex; k < candidates.length  - 1; k++) {

                if (k > startIndex && candidates[k + 1] == candidates[k]) {
                    continue;
                }


                test(candidates, ans, k + 1, resultLists, copy);
            }


        }


    }

}
